#include <cstdint>
#include <string>

#if defined(__GNUC__)
#define CXX_STANDARD	__cplusplus
#elif defined(_MSC_VER)
#define CXX_STANDARD	_MSVC_LANG
#endif

#define ENABLE_OPT defined(__128__OPT__) && (defined(__x86_64__) || defined(_MSC_VER) || defined(__aarch64__))

//允许和128类型进行操作的类型
template <typename T>
struct is_enable_type {
	static constexpr bool value =
		std::is_same<T, int8_t>::value||
		std::is_same<T, uint8_t>::value||
		std::is_same<T, int16_t>::value||
		std::is_same<T, uint16_t>::value||
		std::is_same<T, int32_t>::value||
		std::is_same<T, uint32_t>::value||
		std::is_same<T, int64_t>::value||
		std::is_same<T, uint64_t>::value||
		std::is_same<T, long long>::value||
		std::is_same<T, unsigned long long>::value;
};

// 暂时先不用namespace，考虑到外部测试
class Int128
{

/******************************** ctor **************************/
public:
Int128():high(0),low(0){}
Int128(int32_t v):high(v<0?-1:0),low(static_cast<uint64_t>(v)){}
Int128(int64_t v):high(v<0?-1:0),low(static_cast<uint64_t>(v)){}
Int128(uint32_t v):high(0),low(static_cast<uint64_t>(v)){}
Int128(uint64_t v):high(0),low(static_cast<uint64_t>(v)){}
template <typename T,typename std::enable_if<is_enable_type<T>::value,Int128>::type* dummy=nullptr>
Int128(T v) {
#if CXX_STANDARD >= 201703L
	if constexpr (std::is_integral<T>::value) {
		if constexpr (std::is_signed<T>::value) {
			high = v < 0 ? -1 : 0;
		}
		else {
			high = 0;
		}
		low = static_cast<uint64_t>(v);
	}
#else
	if (std::is_integral<T>::value) {
		if (std::is_signed<T>::value) {
			high = v < 0 ? -1 : 0;
		}
		else {
			high = 0;
		}
		low = static_cast<uint64_t>(v);
	}
#endif
}
#if defined(__GNUC__)
Int128 (__int128 v) {
	this->high = v>>64;
	this->low = v&0xffffffffffffffffll;
}
#endif

private:
Int128(int64_t h, uint64_t d):high(h),low(d){}

public:
Int128(const Int128 &) = default;
Int128(Int128 &&) = default;

public:
~Int128() = default;
/****************************************************************/

/******************************** 赋值 **************************/
public:
Int128 & operator = (const Int128 & rhs)
{
	if(this != &rhs)
	{
        this->high = rhs.high;
		this->low = rhs.low;
	}
	return *this;
}

template <typename T>
typename std::enable_if<is_enable_type<T>::value, Int128 & >::type
operator = (const T & rhs) {
	if (std::is_unsigned<T>::value) {
		this->high = 0;
	}
	else {
		this->high = 0xffffffffffffffff;
	}
	this->low = static_cast<uint64_t>(rhs);
	return *this;
}

Int128 & operator = (Int128 && rhs) noexcept
{
	if(this != &rhs)
	{
        this->high = rhs.high;
		this->low = rhs.low;
	}
	return *this;
}

template <typename T>
typename std::enable_if<is_enable_type<T>::value, Int128 & >::type
operator = (const T && rhs) {
	if (std::is_unsigned<T>::value) {
		this->high = 0;
	}
	else {
		this->high = 0xffffffffffffffff;
	}
	this->low = static_cast<uint64_t>(rhs);
	return *this;
}
/****************************************************************/

/******************************** 正负号 **************************/
public:
Int128 operator + () const {return *this;}
// 负号运算符，取反加一
Int128 operator - () const {return Int128(~this->high, ~this->low) += Int128::one();}
/****************************************************************/

/******************************** 自增自减 **************************/
public:
// 前缀加加
Int128 & operator ++ ()
{
	low = low + 1;
	if (low > 0) {
		return *this;
	}
	high = high + 1;
	return *this;
}
// 后缀加加，原对象要改变，不能是const
Int128 operator ++ (int)
{
	Int128 tmp(high,low);
	++*this;
	return tmp;
}
// 前缀减减
Int128 & operator -- ()
{
	low = low - 1;
	if (low < 0xffffffff) {
		return *this;
	}
	high = high - 1;
	return *this;
}
// 后缀减减，原对象要改变，不能是const
Int128 operator -- (int)
{
	Int128 tmp(high,low);
	--*this;
	return tmp;
}
/****************************************************************/

/******************************** 位非 **************************/
public:
Int128 operator ~ () const
{
	return {~high, ~low};
}
/****************************************************************/

/******************************** 转型 **************************/
/**
 * 类型转换不改变原类型的值
 */
public:
// 向bool转型
operator bool () const
{
	return high != 0 || low != 0;
}
// 向int32转型
operator int32_t () const
{
	return low&0xffffffff;
}
// 向u32转型
operator uint32_t () const
{
	return low&0xffffffff;
}
// 向i64转型
operator int64_t () const
{
	return low&0xffffffffffffffff;
}
// 向u64转型
operator uint64_t () const
{
	return low;
}
//向其余类型转换
template <typename T,typename std::enable_if<is_enable_type<T>::value, Int128>::type* dummy=nullptr>
operator T () const {
	return static_cast<T>(low);
}
#if defined(__GNUC__)
operator __int128 () const {
	__int128 sum=this->high;
	sum <<= 64;
	sum |= this->low;
	return sum;
}
#endif
/****************************************************************/

/******************************** 算术赋值 **************************/
public:
Int128 & operator += (const Int128 & rhs)
{
	auto tmp = this->low;
    this->low += rhs.low;
	this->high += rhs.high;
	if(this->low < tmp) ++this->high;
	return *this;
}

// template <typename T>
// typename std::enable_if<is_enable_type<T>::value, Int128 & >::type
// operator += (const T & rhs) {
// 	if (std::is_unsigned<T>::value || rhs >= 0) {
// 		auto tmp = this->low;
// 		this->low += rhs;
// 		if(this->low < tmp) ++this->high;
// 	}
// 	else {
// 		auto tmp = this->low;
// 		this->low -= (~rhs)+1;
// 		if(tmp < this->low) --this->high;
// 		return *this;
// 	}
// 	return *this;
// }

// template <typename T>
// friend typename std::enable_if<is_enable_type<T>::value, T &>::type
// operator += (T& lhs,const Int128 & rhs) {
// 	lhs += rhs.low;
// 	return lhs;
// }

Int128 & operator -= (const Int128 & rhs)
{
	auto tmp = this->low;
    this->low -= rhs.low;
	this->high -= rhs.high;
	if(tmp < this->low) --this->high;
	return *this;
}

// template <typename T>
// typename std::enable_if<is_enable_type<T>::value, Int128 & >::type
// operator -= (const T & rhs) {
// 	if (std::is_unsigned<T>::value || rhs >= 0) {
// 		auto tmp = this->low;
// 		this->low -= rhs;
// 		if(this->low > tmp) --this->high;
// 	}
// 	else {
// 		auto tmp = this->low;
// 		this->low += (~rhs)+1;
// 		if(tmp > this->low) ++this->high;
// 		return *this;
// 	}
// 	return *this;
// }

// template <typename T>
// friend typename std::enable_if<is_enable_type<T>::value, T &>::type
// operator -= (T& lhs,const Int128 & rhs) {
// 	lhs -= rhs.low;
// 	return lhs;
// }


Int128 & operator *= (const Int128 & rhs)
{
#if ENABLE_OPT
	Int128 a=*this, b=rhs;
	int flag=0;

	if (this->high < 0) {
		a = -*this;
		flag ^= 1;
	}

	if (rhs.high < 0) {
		b = -rhs;
		flag ^= 1;
	}

	uint64_t ans_low, ans_high;
	mul(&ans_high, &ans_low,a.low,b.low);
	this->low = ans_low;
	this->high = ans_high;
	mul(&ans_high, &ans_low,a.low,b.high);
	this->high += ans_low;
	mul(&ans_high, &ans_low,a.high,b.low);
	this->high += ans_low;
	if (flag) {
		*this = -*this;
	}
#else
	// 取补码
	Int128 a = ++(~*this);
	Int128 b = rhs.get_complement();

	// 将this清零
	this->clear();
	for (int i=0;i<128;++i)
	{
		if(b.low & 1) this->operator+=(a);
		a.leftShiftOne();
		b.rightShiftOne();
	}
#endif
	return *this;
}

// template <typename T>
// typename std::enable_if<is_enable_type<T>::value, Int128 & >::type
// operator *= (const T & rhs) {
// #if defined(__x86_64__) || defined(_MSC_VER) || defined(__aarch64__)
// 	Int128 a=*this, b=rhs;
// 	int flag=0;

// 	if (this->high < 0) {
// 		a = -*this;
// 		flag ^= 1;
// 	}

// 	if (rhs.high < 0) {
// 		b = -rhs;
// 		flag ^= 1;
// 	}

// 	uint64_t ans_low, ans_high;
// 	mul(&ans_high, &ans_low,a.low,b.low);
// 	this->low = ans_low;
// 	this->high = ans_high;
// 	mul(&ans_high, &ans_low,a.high,b.low);
// 	this->high += ans_low;
// 	if (flag) {
// 		*this = -*this;
// 	}
// #else
// 	Int128 a = ++(~*this);
// 	T b = std::is_signed<T>::value ? (~rhs) + 1 : rhs;

// 	// 将this清零
// 	this->clear();
// 	for (int i=0;i<128;++i){
// 		if(b & 1) this->operator+=(a);
// 		a.leftShiftOne();
// 		b >>= 1;
// 	}
// #endif
// 	return *this;
// }

// template <typename T>
// friend typename std::enable_if<is_enable_type<T>::value, T &>::type
// operator *= (T& lhs,const Int128 & rhs) {
// 	lhs *= rhs.low;
// 	return lhs;
// }

Int128 & operator /= (const Int128 & rhs)
{
    Int128 quotient, remainder;
	this->divideAndMod(rhs, quotient, remainder);
	return *this = quotient;
}

// template <typename T>
// typename std::enable_if<is_enable_type<T>::value, Int128 & >::type
// operator /= (const T & rhs) {
// 	Int128 quotient, remainder;
// 	this->divideAndMod(rhs, quotient, remainder);
// 	return *this = quotient;
// }

// template <typename T>
// friend typename std::enable_if<is_enable_type<T>::value, T &>::type
// operator /= (T& lhs,const Int128 & rhs) {
// 	//除数的绝对值比被除数大
// 	if (rhs.high != 0) {
// 		lhs = 0;
// 	}
// 	else {
// 		lhs /= rhs.low;
// 	}
// 	return lhs;
// }

Int128 & operator %= (const Int128 & rhs)
{
    Int128 quotient, remainder;
	this->divideAndMod(rhs, quotient, remainder);
	return *this = remainder;
}

// template <typename T>
// typename std::enable_if<is_enable_type<T>::value, Int128 & >::type
// operator %= (const T & rhs) {
// 	Int128 quotient, remainder;
// 	this->divideAndMod(rhs, quotient, remainder);
// 	return *this = remainder;
// }

// template <typename T>
// friend typename std::enable_if<is_enable_type<T>::value, T &>::type
// operator %= (T& lhs,const Int128 & rhs) {
// 	//除数的绝对值比被除数大
// 	if (rhs.high == 0) {
// 		lhs %= rhs.low;
// 	}
// 	return lhs;
// }
/****************************************************************/

/******************************** 位运算赋值 **************************/
public:
Int128 & operator &= (const Int128 & rhs)
{
	this->high &= rhs.high;
	this->low &= rhs.low;
    return *this;
}

// template <typename T>
// typename std::enable_if<is_enable_type<T>::value, Int128 & >::type
// operator &= (const T & rhs) {
// 	this->low &= rhs;
// 	return *this;
// }

Int128 & operator |= (const Int128 & rhs)
{
	this->high |= rhs.high;
	this->low |= rhs.low;
    return *this;
}

// template <typename T>
// typename std::enable_if<is_enable_type<T>::value, Int128 & >::type
// operator |= (const T & rhs) {
// 	this->low |= rhs;
// 	return *this;
// }

Int128 & operator ^= (const Int128 & rhs)
{
	this->high ^= rhs.high;
	this->low ^= rhs.low;
    return *this;
}

// template <typename T>
// typename std::enable_if<is_enable_type<T>::value, Int128 & >::type
// operator ^= (const T & rhs) {
// 	this->low ^= rhs;
// 	return *this;
// }

/**
 * @brief 左移操作
 * @param rhs rhs为负时，行为未定义
 * @return Int128&
 */
Int128 & operator <<= (const Int128 & rhs)
{
	//除了最低的7位，其余位有数值，则返回0，这里认为左移负数返回0
	if ((rhs.high&0xffffffff) + (rhs.low&0xffffff80) > 0) {
		this->high = 0;
		this->low = 0;
		return *this;
	}
	int count = rhs.low&0x7f;
	//如果不小于64位
	if (count >= 0x3f) {
		this->high = this->low << (count-0x3f);
		this->low = 0;
		return *this;
	}
	//把high的低count位让出来
	this->high = this->high << count;
	//把high的低count位变成low的高count位
	this->high |= (this->low>>(64-count))&low_bit[count];
	this->low = this->low >> count;
	return *this;
}

// template <typename T>
// typename std::enable_if<is_enable_type<T>::value, Int128 & >::type
// operator <<= (const T & rhs) {
// 	if (rhs < 0) {
// 		this->high = 0;
// 		this->low = 0;
// 		return *this;
// 	}
// 	int count = rhs&0x7f;
// 	//如果不小于64位
// 	if (count >= 0x3f) {
// 		this->high = this->low << (count-0x3f);
// 		this->low = 0;
// 		return *this;
// 	}
// 	//把high的低count位让出来
// 	this->high = this->high << count;
// 	//把high的低count位变成low的高count位
// 	this->high |= ((this->low>>(64-count))&low_bit[count]);
// 	this->low = this->low << count;
// 	return *this;
// }

Int128 & operator >>= (const Int128 & rhs)
{
	//右移负数认为结果为0
	if (rhs.high < 0) {
		this->high = 0;
		this->low = 0;
		return *this;
	}
	//除了最低的7位，其余位有数值
	if ((rhs.high&0xffffffff) + (rhs.low&0xffffff80) > 0) {
		this->high = this->high >> 64;
		this->low = this->high;
		return *this;
	}
	int count = rhs.low&0x7f;
	//如果不小于64位
	if (count >= 0x3f) {
		this->low = 0;
		this->high = this->high >> 0x3f;
		return *this;
	}
	//把low的高count位让出来
	this->low = this->low >> count;
	//把low的高count位变成high的低count位
	this->low |= this->high&low_bit[count];
	this->high = this->high >> count;
	return *this;
}

// template <typename T>
// typename std::enable_if<is_enable_type<T>::value, Int128 & >::type
// operator >>= (const T & rhs) {
// 	//右移负数认为结果为0
// 	if (rhs < 0) {
// 		this->high = 0;
// 		this->low = 0;
// 		return *this;
// 	}
// 	//除了最低的7位，其余位有数值
// 	if ((rhs&0xffffff80) > 0) {
// 		this->high = this->high >> 64;
// 		this->low = this->high;
// 		return *this;
// 	}
// 	int count = rhs&0x7f;
// 	//如果不小于64位
// 	if (count >= 0x3f) {
// 		this->low = 0;
// 		this->high = this->high >> 0x3f;
// 		return *this;
// 	}
// 	//把low的高count位让出来
// 	this->low = this->low >> count;
// 	//把low的高count位变成high的低count位
// 	this->low |= this->high&low_bit[count];
// 	this->high = this->high >> count;
// 	return *this;
// }
/****************************************************************/

/******************************** 比较 **************************/
public:
/**
 * @brief 比较
 * @param rhs
 * @return
 *    this < rhs 返回-1
 *    this == rhs 返回0
 *    this > rhs 返回+1
 */
int compare(const Int128 & rhs) const
{
    if (this->high != rhs.high) return this->high < rhs.high ? -1 : 1;
	if (this->low != rhs.low) return this->low < rhs.low ? -1 : 1;
	return 0;
}

template <typename T>
typename std::enable_if<is_enable_type<T>::value, int>::type
compare(const T & rhs) const {
	Int128 tmp = *this-rhs;
	if (tmp.high < 0) return -1;
	if (tmp.high==0 && tmp.low == 0) return 0;
	return 1;
}
/****************************************************************/
/******************************** 字符串 **************************/
public:
// 返回10进制表示的字符串
std::string toString() const
{
    return this->toDecString();
}
// 返回16进制表示的字符串
std::string toHexString() const
{
	if (this->high==0&&this->low==0) {
		return "0x0";
	}
	std::string ans="0x";
	bool flag=false;
	for (int i=60;i>=0;i=i-4) {
		if (flag==true) {
			ans+=hex_digit[(this->high>>i)&0xf];
		}
		else if ((this->high>>i)&0xf > 0){
			ans+=hex_digit[(this->high>>i)&0xf];
			flag=true;
		}
	}
	for (int i=60;i>=0;i=i-4) {
		if (flag==true) {
			ans+=hex_digit[(this->low>>i)&0xf];
		}
		else if ((this->low>>i)&0xf > 0){
			ans+=hex_digit[(this->low>>i)&0xf];
			flag=true;
		}
	}
	return ans;
}
// 返回10进制表示的字符串
std::string toDecString() const
{
	if (this->high==0&&this->low==0) {
		return "0";
	}
	std::string ans="";
	auto tmp = this->high < 0 ? ++(~*this) : *this;
	if (this->high < 0) {
		ans += "-";
	}
	while (tmp.high > 0 || tmp.low >= 100) {
		auto const num = (tmp.low % 100) * 2;
		tmp /= 100;
		ans += digits[num + 1];
		ans += digits[num];
	}
	if (tmp.low >= 10) {
		auto const num = tmp.low * 2;
		ans += digits[num + 1];
		ans += digits[num];
	}
	else {
		auto const num = tmp.low * 2;
		ans += digits[num + 1];
	}
	for (int i=1,j=ans.size()-1;i<j;++i,--j) {
		std::swap(ans[i],ans[j]);
	}
	return ans;
}
/****************************************************************/

/******************************** 静态 **************************/
public:
static Int128 one() {static const Int128 ONE(1); return ONE;}
static Int128 zero() {static const Int128 ZERO(0); return ZERO;}
/****************************************************************/

/******************************** 私有 **************************/
private:
bool isNegative() const {return this->high < 0;}
bool isZero() const {return 0 == this->high and 0 == this->low;}
// 左移一位
void leftShiftOne()
{
    this->high <<= 1;
	this->high |= this->low >> 63;
	this->low <<= 1;
}
// 右移一位
void rightShiftOne()
{
	this->low >>= 1;
	this->low |= static_cast<uint64_t>(this->high) << 63;
	this->high >>= 1;
}

// 计算 this / rhs，商保存在quotient, 余数保存在 remainder
void divideAndMod(const Int128 & rhs, Int128 & quotient, Int128 & remainder) const
{
    if(rhs.isZero())
	{
		remainder.high = remainder.low = 0;
		quotient.high = quotient.low = 1 / 0; // 异常交给系统处理
		return;
	}

	// 清零
	quotient.clear();
	remainder.clear();

	auto tl = this->high < 0 ? -*this : *this;
	auto tr = rhs.high < 0 ? -rhs : rhs;

#if ENABLE_OPT
	if (tr.high == 0) {
		uint64_t ans_high, ans_low;
		uint64_t tl_high=tl.high, r_high, r_low=0;
		//计算high/d
		ans_high = div(&r_low, &tl_high, &tr.low, r_high);
		ans_low = div(&r_high, &tl.low,&tr.low,r_low);
		remainder.high = r_high;
		remainder.low = r_low;
		quotient.high = ans_high;
		quotient.low = ans_low;
	}
	else {
		remainder.low = tl.high;
		for(int i=63;i>=0;--i)
		{
			quotient <<= 1;
			remainder <<= 1;
			remainder |= ((tl.low>>i)&1);

			if (remainder.compare(tr) >= 0) {
				remainder -= tr;
				quotient.low |= 1;
			}
		}
	}
#else
	for(int i=126;i>=0;--i)
	{
		quotient <<= 1;
		remainder <<= 1;
		if (i>=64) {
			remainder |= ((tl.high>>(i-64))&1);
		}
		else {
			remainder |= ((tl.low>>i)&1);
		}

		if (remainder.compare(tr) >= 0) {
			remainder -= tr;
			quotient.low |= 1;
		}
	}
#endif

	if ((this->high < 0) ^ (rhs.high < 0) == 1) {
		quotient = -quotient;
	}
	if (this->high < 0) {
		remainder = -remainder;
	}
}

template <typename T>
typename std::enable_if<is_enable_type<T>::value, void>::type
divideAndMod(const T & rhs, Int128 & quotient, Int128 & remainder) const {
	if(rhs == 0)
	{
		remainder.high = remainder.low = 0;
		quotient.high = quotient.low = 1 / 0; // 异常交给系统处理
		return;
	}

	// 清零
	quotient.clear();
	remainder.clear();

	auto tl = this->high < 0 ? -*this : *this;
	uint64_t tr = rhs < 0 ? -rhs : rhs;

#if ENABLE_OPT
	uint64_t ans_high, ans_low;
	uint64_t tl_high=tl.high, r_high, r_low=0;
	//计算high/d
	ans_high = div(&r_low, &tl_high, &tr, r_high);
	ans_low = div(&r_high, &tl.low,&tr,r_low);
	remainder.high = r_high;
	remainder.low = r_low;
	quotient.high = ans_high;
	quotient.low = ans_low;
#else
	for(int i=126;i>=0;--i)
	{
		quotient <<= 1;
		remainder <<= 1;
		if (i>=64) {
			remainder |= ((tl.high>>(i-64))&1);
		}
		else {
			remainder |= ((tl.low>>i)&1);
		}

		if (remainder.compare(tr) >= 0) {
			remainder -= tr;
			quotient.low |= 1;
		}
	}
#endif

	if ((this->high < 0) ^ (rhs < 0) == 1) {
		quotient = -quotient;
	}
	if (this->high < 0) {
		remainder = -remainder;
	}
}

void clear(){this->high = this->low = 0;}

//获取补码
Int128 get_complement() const {
	Int128 ans(~this->high,~this->low);
	return ++ans;
}
/****************************************************************/
public:

//内联汇编接口
#if defined(__x86_64__)

#if defined (__GNUC__)
void mul(uint64_t* high,uint64_t* low, uint64_t x,uint64_t y) {
	asm volatile(
		//使用rdi(x)和rsi(y)进行乘法
		"mulq %%rsi\n\t"
		//此时rax是低64位，rdx是高64位
		:"=d"(*high), "=a"(*low)
		:"a"(x), "S"(y)
		:"cc", "memory"
	);
}

uint64_t div(uint64_t* high, uint64_t* low,uint64_t* d, uint64_t& remainder) const {
	uint64_t q;
	asm volatile(
		"divq %3"
		: "=a"(q), "=d"(remainder)
		:"a"(*low), "r"(*d), "d"(*high)
		:"cc"
	);
	return q;
}
#elif #defined(_MSC_VER)
void mul(uint64_t* high,uint64_t* low, uint64_t x,uint64_t y) {
	//msvc中有内置的128函数
	low = _umul128(x, y, &high);
}

uint64_t div(uint64_t* high, uint64_t* low,uint64_t* d, uint64_t& remainder) const {
	return _udiv128(*high, *low, d, remainder());
}
#endif

#elif defined(__aarch64__)
void mul(uint64_t* high,uint64_t* low, uint64_t x,uint64_t y) {
	asm volatile(
		//低位乘法
		"mul %0, %1, %2\n\t"
		//高位乘法
		"umulh %3, %1, %2\n\t"
		: "=r"(*low), "=r"(*high)
		: "=r"(x), "=r"(y)
	);
}

uint64_t div(uint64_t* high, uint64_t* low,uint64_t* d, uint64_t& remainder) const {
	__int128 tmp = high;
	tmp<<=64;
	tmp+=low;
	remainder = tmp%d;
	return tmp/d;
}
#endif

int64_t high; // 高位带符号
uint64_t low; // 低位无符号

const char hex_digit[17] = {"0123456789abcdef"};

const uint64_t low_bit[65]={
	0,
	0x0000000000000001,0x0000000000000003,0x0000000000000007,0x000000000000000f,
	0x000000000000001f,0x000000000000003f,0x000000000000007f,0x00000000000000ff,
	0x00000000000001ff,0x00000000000003ff,0x00000000000007ff,0x0000000000000fff,
	0x0000000000001fff,0x0000000000003fff,0x0000000000007fff,0x000000000000ffff,
	0x000000000001ffff,0x000000000003ffff,0x000000000007ffff,0x00000000000fffff,
	0x00000000001fffff,0x00000000003fffff,0x00000000007fffff,0x0000000000ffffff,
	0x0000000001ffffff,0x0000000003ffffff,0x0000000007ffffff,0x000000000fffffff,
	0x000000001fffffff,0x000000003fffffff,0x000000007fffffff,0x00000000ffffffff,
	0x00000001ffffffff,0x00000003ffffffff,0x00000007ffffffff,0x0000000fffffffff,
	0x0000001fffffffff,0x0000003fffffffff,0x0000007fffffffff,0x000000ffffffffff,
	0x000001ffffffffff,0x000003ffffffffff,0x000007ffffffffff,0x00000fffffffffff,
	0x00001fffffffffff,0x00003fffffffffff,0x00007fffffffffff,0x0000ffffffffffff,
	0x0001ffffffffffff,0x0003ffffffffffff,0x0007ffffffffffff,0x000fffffffffffff,
	0x001fffffffffffff,0x003fffffffffffff,0x007fffffffffffff,0x00ffffffffffffff,
	0x01ffffffffffffff,0x03ffffffffffffff,0x07ffffffffffffff,0x0fffffffffffffff,
	0x1fffffffffffffff,0x3fffffffffffffff,0x7fffffffffffffff,0xffffffffffffffff,
};

const char digits[201] =
	"0001020304050607080910111213141516171819"
	"2021222324252627282930313233343536373839"
	"4041424344454647484950515253545556575859"
	"6061626364656667686970717273747576777879"
	"8081828384858687888990919293949596979899";

};



/******************************** 算术运算 **************************/
inline Int128 operator + (const Int128 & lhs, const Int128 & rhs)
{
	return Int128(lhs) += rhs;
}

template <typename T>
typename std::enable_if<is_enable_type<T>::value,Int128>::type
operator + (const Int128 & lhs, const T & rhs) {
	return Int128(lhs) += rhs;
}

template <typename T>
typename std::enable_if<is_enable_type<T>::value,Int128>::type
operator + (const T & lhs, const Int128 & rhs) {
	return Int128(lhs) += rhs;
}

inline Int128 operator - (const Int128 & lhs, const Int128 & rhs)
{
	return Int128(lhs) -= rhs;
}

template <typename T>
typename std::enable_if<is_enable_type<T>::value,Int128>::type
operator - (const Int128 & lhs, const T & rhs) {
	return Int128(lhs) -= rhs;
}

template <typename T>
typename std::enable_if<is_enable_type<T>::value,Int128>::type
operator - (const T & lhs, const Int128 & rhs) {
	return Int128(lhs) -= rhs;
}

inline Int128 operator * (const Int128 & lhs, const Int128 & rhs)
{
	return Int128(lhs) *= rhs;
}

template <typename T>
typename std::enable_if<is_enable_type<T>::value,Int128>::type
operator * (const Int128 & lhs, const T & rhs) {
	return Int128(lhs) *= rhs;
}

template <typename T>
typename std::enable_if<is_enable_type<T>::value,Int128>::type
operator * (const T & lhs, const Int128 & rhs) {
	return Int128(lhs) *= rhs;
}

inline Int128 operator / (const Int128 & lhs, const Int128 & rhs)
{
	return Int128(lhs) /= rhs;
}

template <typename T>
typename std::enable_if<is_enable_type<T>::value,Int128>::type
operator / (const Int128 & lhs, const T & rhs) {
	return Int128(lhs) /= rhs;
}

template <typename T>
typename std::enable_if<is_enable_type<T>::value,Int128>::type
operator / (const T & lhs, const Int128 & rhs) {
	return Int128(lhs) /= rhs;
}

inline Int128 operator % (const Int128 & lhs, const Int128 & rhs)
{
	return Int128(lhs) %= rhs;
}

template <typename T>
typename std::enable_if<is_enable_type<T>::value,Int128>::type
operator % (const Int128 & lhs, const T & rhs) {
	return Int128(lhs) %= rhs;
}

template <typename T>
typename std::enable_if<is_enable_type<T>::value,Int128>::type
operator % (const T & lhs, const Int128 & rhs) {
	return Int128(lhs) %= rhs;
}
/****************************************************************/
/******************************** 关系运算 **************************/
inline bool operator < (const Int128 & lhs, const Int128 & rhs)
{
	return -1 == lhs.compare(rhs);
}

template <typename T>
typename std::enable_if<is_enable_type<T>::value,bool>::type
operator < (const Int128 & lhs, const T & rhs) {
	return -1 == lhs.compare(rhs);
}

template <typename T>
typename std::enable_if<is_enable_type<T>::value,bool>::type
operator < (const T & lhs, const Int128 & rhs) {
	return rhs.compare(lhs) == 1;
}

inline bool operator == (const Int128 & lhs, const Int128 & rhs)
{
	return 0 == lhs.compare(rhs);
}

template <typename T>
typename std::enable_if<is_enable_type<T>::value,bool>::type
operator == (const Int128 & lhs, const T & rhs) {
	return 0 == lhs.compare(rhs);
}

template <typename T>
typename std::enable_if<is_enable_type<T>::value,bool>::type
operator == (const T & lhs, const Int128 & rhs) {
	return 0 == rhs.compare(lhs);
}

inline bool operator <= (const Int128 & lhs, const Int128 & rhs)
{
	return lhs.compare(rhs) <= 0;
}

template <typename T>
typename std::enable_if<is_enable_type<T>::value,bool>::type
operator <= (const Int128 & lhs, const T & rhs) {
	return lhs.compare(rhs) <= 0;
}

template <typename T>
typename std::enable_if<is_enable_type<T>::value,bool>::type
operator <= (const T & lhs, const Int128 & rhs) {
	return rhs.compare(lhs) >= 0;
}

inline bool operator != (const Int128 & lhs, const Int128 & rhs)
{
	return 0 != lhs.compare(rhs);
}

template <typename T>
typename std::enable_if<is_enable_type<T>::value,bool>::type
operator != (const Int128 & lhs, const T & rhs) {
	return 0 != lhs.compare(rhs);
}

template <typename T>
typename std::enable_if<is_enable_type<T>::value,bool>::type
operator != (const T & lhs, const Int128 & rhs) {
	return 0 != rhs.compare(lhs);
}

inline bool operator > (const Int128 & lhs, const Int128 & rhs)
{
	return 1 == lhs.compare(rhs);
}

template <typename T>
typename std::enable_if<is_enable_type<T>::value,bool>::type
operator > (const Int128 & lhs, const T & rhs) {
	return 1 == lhs.compare(rhs);
}

template <typename T>
typename std::enable_if<is_enable_type<T>::value,bool>::type
operator > (const T & lhs, const Int128 & rhs) {
	return -1 == rhs.compare(lhs);
}

inline bool operator >= (const Int128 & lhs, const Int128 & rhs)
{
	return 0 <= lhs.compare(rhs);
}

template <typename T>
typename std::enable_if<is_enable_type<T>::value,bool>::type
operator >= (const Int128 & lhs, const T & rhs) {
	return 0 <= lhs.compare(rhs);
}

template <typename T>
typename std::enable_if<is_enable_type<T>::value,bool>::type
operator >= (const T & lhs, const Int128 & rhs) {
	return 0 >= rhs.compare(lhs);
}

/****************************************************************/

/******************************** 位运算 **************************/
inline Int128 operator ^ (const Int128 & lhs, const Int128 & rhs)
{
	return Int128(lhs) ^= rhs;
}

// template <typename T>
// typename std::enable_if<is_enable_type<T>::value,Int128>::type
// operator ^ (const Int128 & lhs, const T & rhs) {
// 	return Int128(lhs) ^= rhs;
// }

// template <typename T>
// typename std::enable_if<is_enable_type<T>::value,Int128>::type
// operator ^ (const T & lhs, const Int128 & rhs) {
// 	return Int128(lhs) ^= rhs;
// }

inline Int128 operator & (const Int128 & lhs, const Int128 & rhs)
{
	return Int128(lhs) &= rhs;
}

// template <typename T>
// typename std::enable_if<is_enable_type<T>::value,Int128>::type
// operator & (const Int128 & lhs, const T & rhs) {
// 	return Int128(lhs) &= rhs;
// }

// template <typename T>
// typename std::enable_if<is_enable_type<T>::value,Int128>::type
// operator & (const T & lhs, const Int128 & rhs) {
// 	return Int128(lhs) &= rhs;
// }

inline Int128 operator | (const Int128 & lhs, const Int128 & rhs)
{
	return Int128(lhs) |= rhs;
}

// template <typename T>
// typename std::enable_if<is_enable_type<T>::value,Int128>::type
// operator | (const Int128 & lhs, const T & rhs) {
// 	return Int128(lhs) |= rhs;
// }

// template <typename T>
// typename std::enable_if<is_enable_type<T>::value,Int128>::type
// operator | (const T & lhs, const Int128 & rhs) {
// 	return Int128(lhs) |= rhs;
// }
/****************************************************************/
/******************************** 移位运算 **************************/
inline Int128 operator << (const Int128 & lhs, const Int128 & rhs)
{
	return Int128(lhs) <<= rhs;
}

// template <typename T>
// typename std::enable_if<is_enable_type<T>::value,Int128>::type
// operator << (const Int128 & lhs, const T & rhs) {
// 	return Int128(lhs) <<= rhs;
// }

// template <typename T>
// typename std::enable_if<is_enable_type<T>::value,Int128>::type
// operator << (const T & lhs, const Int128 & rhs) {
// 	return Int128(lhs) <<= rhs;
// }

inline Int128 operator >> (const Int128 & lhs, const Int128 & rhs)
{
	return Int128(lhs) >>= rhs;
}

// template <typename T>
// typename std::enable_if<is_enable_type<T>::value,Int128>::type
// operator >> (const Int128 & lhs, const T & rhs) {
// 	return Int128(lhs) >>= rhs;
// }

// template <typename T>
// typename std::enable_if<is_enable_type<T>::value,Int128>::type
// operator >> (const T & lhs, const Int128 & rhs) {
// 	return Int128(lhs) >>= rhs;
// }
/****************************************************************/

/******************************** 流输出运算 **************************/
inline std::ostream & operator << (std::ostream & os, const Int128 & rhs)
{
	return os << rhs.toString();
}

/****************************************************************/

